#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    long long mostPoints(vector<vector<int>> &questions)
    {
        // questions[i] = [pointsi, brainpoweri]

        vector<long long> dp(questions.size(), 0);
        dp[questions.size() - 1] = questions[questions.size() - 1][0];
        for (int i = questions.size() - 2; i >= 0; i--)
        {
            // skip
            dp[i] = dp[i + 1];
            // choose
            if (i + questions[i][1] + 1 < questions.size())
                dp[i] = max(dp[i], questions[i][0] + dp[i + questions[i][1] + 1]);
            else
                dp[i] = max(dp[i], static_cast<long long>(questions[i][0]));
        }
        return dp[0];
    }
};

int main()
{
    cout << "Code2140" << endl;
    Solution s;
    vector<vector<int>> questions = {{12, 46}, {78, 19}, {63, 15}, {79, 62}, {13, 10}};
    cout << s.mostPoints(questions) << endl;
    return 0;
}
/*
O(n2)
class Solution
{
public:
    long long mostPoints(vector<vector<int>> &questions)
    {
        // questions[i] = [pointsi, brainpoweri]

        vector<long long> dp(questions.size(), 0);
        dp[questions.size() - 1] = questions[questions.size() - 1][0];
        for (int i = questions.size() - 2; i >= 0; i--)
        {
            // skip
            dp[i] = dp[i + 1];
            // choose
            for (int k = i + questions[i][1] + 1; k < questions.size(); k++)
            {
                dp[i] = max(dp[i], questions[i][0] + dp[k]);
            }
            dp[i] = max(dp[i], static_cast<long long>(questions[i][0]));
        }
        return dp[0];
    }
};
*/